class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        # isPalindrome[i][j]用于表示闭区间子串[i,j]是否是回文
        isPalindrome = [[True] * n for _ in range(n)]
        for i in range(n - 1)[::-1]:
            for j in range(i + 1, n):
                # 对于当前子串[i,j], 如果s[i]==s[j]且子串[i+1,j-1]是回文, 则当前子串也是回文
                # 外层循环倒序, 内层循环正序, 这样可以保证isPalindrome[i+1][j-1]一定是之前已经求出的值
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] and s[i] == s[j]

        # dp[i]表示以i结尾的最少分割次数, 结果即为dp[-1]
        dp = [float("inf")] * n
        for j in range(n):
            if isPalindrome[0][j]:
                # [0,j]本身就是回文串, 无需分割
                dp[j] = 0
            else:
                for i in range(1, j + 1):
                    # i代表最后一个子串[i,j]的起点
                    if isPalindrome[i][j]:
                        # 如果[i,j]回文的话, dp[j]就可以从dp[i-1]+1转移过来
                        # 因为有多种可能的i, 所以取最小的结果作为dp[j]的值
                        dp[j] = min(dp[j], dp[i - 1] + 1)
        return dp[-1]
